package editor.cn;

import java.util.Arrays;

class Solution123{
    public static void main(String[] args) {
        Solution solution = new Solution123().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int maxProfit(int[] prices) {
        return dp(prices,2);
    }
        //搞不懂这里为什么要用k+2？？而且不用会出错！！
        //因为这里的dp递推式会在右边出现j-1，所以要在前面插入一个状态，那就是要在往后面移动一个状态。
        //那么加上原来的数组0的起始，最终就是返回的f[n][k+1][0]，随意初始化的也就是k+2了！！！
        private int dp(int[] prices,int k) {
            int n = prices.length;
            int[][][] f = new int[n + 1][k + 2][2];
            for (int[][] mat : f) {
                for (int[] row : mat) {
                    Arrays.fill(row, Integer.MIN_VALUE/2); // 防止溢出//这里填充的最小值的1/2就已经完成了边界值的负无穷设置
                }
            }
            for (int j = 1; j <= k + 1; j++) {
                f[0][j][0] = 0;
            }

            for (int i = 0; i < n; i++) {
                for (int j = 1; j <= k + 1; j++) {
                    f[i + 1][j][0] = Math.max(f[i][j][0], f[i][j-1][1] + prices[i]);//卖出赚钱了（定义卖出为一次交易的结束）
                    f[i + 1][j][1] = Math.max(f[i][j][1], f[i][j][0] - prices[i]);  //买入花钱了
                }
            }
            return f[n][k + 1][0];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}